public class Test4 {
    public int numDecodings1(String s) {
        // 优化后 新的 dp 表都往后移动一位， dp[0] 为虚拟结点
        int n = s.length();
        char[] arr = s.toCharArray();
        int[] dp = new int[n + 1];

        // 由于 当dp[0] 和 dp[1] 的解码方式存在时需要加上 dp[0] 所以dp[0] = 1
        dp[0] = 1;
        if(arr[0] != '0') dp[1] = 1;
        if(n == 1) return dp[1];

        for(int i = 2;i <= n;i++) {
            if(arr[i - 1] != '0') dp[i] += dp[i - 1];
            int t = (arr[i - 2] - '0') * 10 + arr[i - 1] - '0';
            if(t >= 10 && t <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];

    }
    public int numDecodings(String s) {
        if(s.length() == 0) return 0;
        if(s.length() == 1) {
            if(s.charAt(0) == '0') return 0;
            else return 1;
        }
        int n = s.length();
        int[] dp = new int[n];
        if(s.charAt(0) == '0') {
            dp[0] = 0;
            dp[1] = 0;
        }else {
            dp[0] = 1;
            if(((s.charAt(0) - '0') * 10) + (s.charAt(1) - '0') <= 26) {
                if(s.charAt(1) != '0') {
                    dp[1] = 2;
                }else {
                    dp[1] = 1;
                }
            }else {
                if(s.charAt(1) != '0') {
                    dp[1] = 1;
                }else {
                    dp[1] = 0;
                }
            }
        }
        System.out.println(dp[0]);
        System.out.println(dp[1]);
        for(int i = 2;i < n;i++) {
            if(s.charAt(i) == '0') {
                if(((s.charAt(i - 1) - '0') * 10) + (s.charAt(i) - '0') <= 26 && s.charAt(i - 1) != '0') {
                    dp[i] = dp[i - 2];
                }else {
                    dp[i] = 0;
                }
            }else {
                if(((s.charAt(i - 1) - '0') * 10) + (s.charAt(i) - '0') <= 26 && s.charAt(i - 1) != '0') {
                    dp[i] = dp[i - 2] + dp[i - 1];
                }else {
                    dp[i] = dp[i - 1];
                }
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        Test4 test4 = new Test4();
        System.out.println(test4.numDecodings("27"));
    }
}
